package main

import (
	"fmt"
)

func numDistinct(s string, t string) int {
	var result int = 0
	tmp := make(map[int][]int)

	if len(s) == len(t) {
		if s == t {
			return 1
		}
		return 0
	}

	if len(t) == 1 {
		for _, v := range s {
			v1 := fmt.Sprintf("%c", v)
			if v1 == t {
				result = result + 1
			}
		}
		return result
	}

	for i := 0; i < len(t); i++ {
		tv := fmt.Sprintf("%c", t[i])
		for j := 0; j < len(s); j++ {
			sv := fmt.Sprintf("%c", s[j])
			if sv == tv {
				tmp[i] = append(tmp[i], j)
			}
		}
	}

	//fmt.Println(tmp)
	return Recursive(tmp, -1, 0, len(t)-1)
}

func main() {
	//fmt.Print(numDistinct("babgbag", "bag"))
	fmt.Print(numDistinct("adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc", "bcddceeeebecbc"))
}

func Recursive(p map[int][]int, f int, l int, n int) (r int) {
	if l == n {
		for _, v := range p[l] {
			if v > f {
				r = r + 1
			}
		}
		return
	}

	if l < n {
		for _, v := range p[l] {
			if v > f {
				r = r + Recursive(p, v, l+1, n)
			}
		}
		return
	}
	return
}
